package com.cuz.daileetcode.utils;

import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.Stream;

/**
 * @author cuzz
 * @version 1.0
 * @description: 单调栈
 * @date 22:40 2021/12/30
 **/
public class MonotoneStack<T> {

    /**
     * 下标记录栈
     * 使用linkedList存储多个相同大小的值的下表
     * 比如 【5，5，5】
     * 对应栈的底部就是 linkedList【0，1.2】
     */
    private Stack<LinkedList<Integer>> indexMemoryStack;
    /***
     * 深拷贝原数组内容
     * 为什么深拷贝，防止后续单调栈使用中 改变原数据导致 栈使用错误
     */
    private T[] sourceDataCopy;

    /**
     * 比较器
     * 你可以传入不同的比较 让栈称为 栈底部到顶部 大——>小 or小——>大
     */
    private Comparator<T> comparator = null;
    /***
     * 记录是否结算过
     * 结算指：数组sourceDataCopy没有剩余元素可以加入到栈中
     * 也就是 curIndex= sourceDataCopy.length
     * 此标志在调用依次后置为true 保证用户无法多次结算
     * 结算将清理掉所以元素
     */
    private boolean hasClear = false;
    /***
     * 当前轮到第几个元素进栈
     */
    private int curIndex = -1;

    private MonotoneStack() {
    }

    /***
     * 深拷贝原数组，初始化单调栈 使用默认的比较策略
     * @param sourceArray 原数组
     * @return MonotoneStack
     */
    public static <T> MonotoneStack<T> create(T[] sourceArray) {
        Objects.requireNonNull(sourceArray);
        MonotoneStack<T> res = new MonotoneStack<>();
        res.indexMemoryStack = new Stack<>();
        res.sourceDataCopy = Arrays.copyOf(sourceArray, sourceArray.length);
        return res;
    }

    /**
     * 支持比较器的 构造方法
     *
     * @param sourceArray 原数组
     * @param comparator  使用的比较器
     * @return MonotoneStack
     */
    public static <T> MonotoneStack<T> create(T[] sourceArray, Comparator<T> comparator) {
        MonotoneStack<T> res = create(sourceArray);
        res.comparator = comparator;
        return res;
    }

    /****
     * 让下一个元素 进栈
     * 将输出 ：
     * 需要出栈元素在元素数组中，左边离自己最近且值大于自己的元素的下标和值 记作 leftInfo
     * 需要出栈元素在元素数组中，右边离自己最近且值大于自己的元素的下标和值 记作 rightInfo
     * 例如：
     * 数组 5，5，3 4
     * 让4进栈 这时候 3 需要出栈才能让栈单调递增
     * 当前栈元素 依次从栈底到栈顶是 两个5的下标{0,1} 3的下标{2}
     * 3 的 leftInfo 是 下标1 值为5 因为下标为1 的5比3大且最近
     * 3的rightInfo 是 下标3 值为4 就是当前需要进栈的元素
     * 如果进栈的时候，栈为空 直接元素值对应下标进栈
     * 如果进栈的时候 元素值和栈顶下标值一样 那么 下标加入到栈顶的链表中
     * 如果进栈的时候 元素值小于栈顶下标对应的值 ，那么自己单独成链表加入到栈顶
     *
     * 如果当前需要清算
     * 比如数组 8 4 3 2 7
     * 最后一个7进栈之后下次调用此方法进入清算阶段
     * 此时栈为 8，7
     * 对于7存在·leftInfo 为 下标为0的8
     * 对应8 存在不存在leftInfo 和 rightInfo
     * 清算将 清空栈 返回所有信息
     * @see PushCausePopInfo
     * @return List<PushCausePopInfo < T33>> 被出栈元素本身的值 和元素 的leftInfo，rightInfo
     */
    public List<PushCausePopInfo<T>> pushNextInto() {
        //当前下标 等于 数组长度-1 也就是无元素可以进栈 且 !hasClear代表没有清算过
        if (curIndex == sourceDataCopy.length - 1 && !hasClear) {
            //改变 标识符
            hasClear = true;
            //返回清算结果
            return remainingElementInStackInfo();
        }
        //判断是否可以进栈 期望进栈元素的下标（curIndex+1）是否小于 sourceDataCopy长度 如果不小于将抛出异常
        checkHasElementCanPush();
        //curIndex++ 下标+1
        curIndex++;
        //返回结果
        List<PushCausePopInfo<T>> pushCausePopInfoList = new ArrayList<>();
        //如果当前元素大于栈顶元素 那么 把需要出栈元素的信息加入到elementPushInfoList
        while (!curElementCanPushOrNot()) {
            pushCausePopInfoList.addAll(popOneGenerateInfo());
        }
        //如果当前栈空 那么 直接加入到栈顶 自己单独成链条
        if (indexMemoryStack.isEmpty()) {
            singleElementPush();
        } else {
            //反之不为空 需要看当前下标对应的值 是否等于栈顶元素下标对应的值
            //栈顶元素的下标
            Integer topElementIndex = indexMemoryStack.peek().getLast();
            //栈顶元素的值
            T topElementValue = sourceDataCopy[topElementIndex];
            //当前进栈元素的值
            T curElementValue = sourceDataCopy[curIndex];
            //如果相等加入到栈顶部下标链表
            if (isEquals(topElementValue, curElementValue)) {
                indexMemoryStack.peek().addLast(curIndex);
            } else {
                //加入到栈顶 自己单独成链条
                singleElementPush();
            }
        }
        //返回出栈元素的信息
        return pushCausePopInfoList;
    }

    /***
     * 当前位置单独成链压栈
     */
    private void singleElementPush() {
        //单独成链 加入栈
        LinkedList<Integer> tempList = new LinkedList<>();
        tempList.addLast(curIndex);
        indexMemoryStack.push(tempList);
    }

    /***
     * 执行清算
     * 比如数组 8 4 3 2 7
     * 最后一个7进栈之后下次调用此方法进入清算阶段
     * 此时栈为 8，7
     * 对于7存在·leftInfo 为 下标为0的8
     * 对应8 存在不存在leftInfo 和 rightInfo
     * 清算将 清空栈 返回所有信息
     * @see #pushNextInto
     * @return List<PushCausePopInfo < T33>> 被清算元素本身的值 和元素 的leftInfo，rightInfo
     */
    private List<PushCausePopInfo<T>> remainingElementInStackInfo() {
        //记录结果集合
        LinkedList<PushCausePopInfo<T>> res = new LinkedList<>();
        //如果栈不为空
        while (!indexMemoryStack.isEmpty()) {
            //拿到所有的栈顶的下标链表 这是当前循环出栈的元下标
            LinkedList<Integer> topElement = indexMemoryStack.pop();
            //循环处理
            for (Integer loopIndex : topElement) {
                //出栈元素的rightInfo肯定时空 因为没有其他元素压栈的，在自己右边无自己大的元素
                PushCausePopInfo<T> tempInfo = PushCausePopInfo
                        .cur(loopIndex, sourceDataCopy)
                        .right(null);
                //如果栈不为空，说明存在leftInfo ，loopIndex的左边存在比自己大的
                if (!indexMemoryStack.isEmpty()) {
                    //拿到最左边和自己最近的 下标
                    Integer leftIndex = indexMemoryStack.peek().getLast();
                    tempInfo.left(leftIndex);
                }
                //加入结果集合
                res.add(tempInfo);
            }
        }
        return res;
    }

    /***
     * 出栈一个元素 生成信息
     *
     * @see PushCausePopInfo
     * @return List<PushCausePopInfo < T33>> 被出栈元素本身的值 和元素 的leftInfo，rightInfo
     */
    private List<PushCausePopInfo<T>> popOneGenerateInfo() {
        //当前出栈的元素右边自己大元素的下标就是curIndex
        int rightIndex = curIndex;
        //弹出
        LinkedList<Integer> indexInfoOnStackTop = indexMemoryStack.pop();
        Stream<PushCausePopInfo<T>> resStream = indexInfoOnStackTop.stream()
                .map(infoIndex -> PushCausePopInfo
                        .cur(infoIndex, sourceDataCopy)
                        .right(rightIndex));
        //如果空 那么 说明没有左侧比自己大的信息
        if (indexMemoryStack.isEmpty()) {
            //直接收集返回
            return resStream.collect(Collectors.toList());
        }
        //反之存在 左侧比自己大的 那么每一个元素设置下左侧比自己大元素的信息 收集返回
        Integer popElementLessThan = indexMemoryStack.peek().getLast();
        return resStream.peek(item -> item.left(popElementLessThan)).collect(Collectors.toList());
    }

    /***
     * 确保元素可以进行压栈 保证curIndex + 1 >= sourceDataCopy.length不成立
     */
    private void checkHasElementCanPush() {
        if (curIndex + 1 >= sourceDataCopy.length) {
            throw new UnsupportedOperationException("无元素可以压入单调栈");
        }
    }

    /**
     * 两个元素是否相等
     * @see #compareResult(Object, Object)
     * @param e1 元素1
     * @param e2 元素2
     * @return
     */
    private boolean isEquals(T e1, T e2) {
        return compareResult(e1, e2) == 0;
    }

    /***
     * 元素比较
     * 优先使用比较器
     * 后进行强转 如果无法转换那么抛出异常
     * @param e1 元素1
     * @param e2 元素2
     * @return 比较结果
     */
    private int compareResult(T e1, T e2) {
        if (Objects.nonNull(comparator)) {
            return comparator.compare(e1, e2);
        } else {
            try {
                Comparable<T> comparableE1 = (Comparable<T>) e1;
                return comparableE1.compareTo(e2);
            } catch (Exception e) {
                throw new UnsupportedOperationException("请传入比较器，或可比较的对象");
            }
        }
    }

    /**
     * 当前元素是否小于当前栈顶元素 是否可以将当前元素进行压栈
     * 若栈为空 那么返回true
     * 如果小于等于栈顶下标的值 那么也可以压栈
     * @see #compareResult(Object, Object)
     * @return  是否可以压栈
     */
    private boolean curElementCanPushOrNot() {
        T curElementNeedPush = sourceDataCopy[curIndex];
        if (indexMemoryStack.isEmpty()) {
            return true;
        }
        LinkedList<Integer> stackToIndexList = indexMemoryStack.peek();
        Integer lastIndexOfTop = stackToIndexList.getLast();
        T elementAtTop = sourceDataCopy[lastIndexOfTop];
        return compareResult(curElementNeedPush, elementAtTop) <= 0;
    }

    /***
     * 压栈导致元素出栈产生的信息
     * @param <T>
     */
    public static class PushCausePopInfo<T> {
        /**
         * 当前元素的下标
         */
        private Integer curElementIndex;
        /**
         * 当前元素的值
         */
        private T curElementValue;
        /**
         *左边大于curElementValue元素的下标
         */
        private Integer leftGreaterElementIndex;
        /**
         *左边大于curElementValue元素的值
         */
        private T leftGreaterElementValue;
        /**
         *右边大于curElementValue元素的下标
         */
        private Integer rightGreaterElementIndex;
        /**
         *右边大于curElementValue元素的值
         */
        private T rightGreaterElementValue;
        /**
         * 缓存数组 避免重复传入
         */
        private T[] sourceDataCopy;

        private PushCausePopInfo() {
        }

        /**
         * 当前被pop元素的下标和 源数组
         * @param curIndex 当前元素的下标
         * @param sourceDataCopy 数组
         * @return PushCausePopInfo
         */
        public static <T> PushCausePopInfo<T> cur(Integer curIndex, T[] sourceDataCopy) {
            PushCausePopInfo<T> res = new PushCausePopInfo<>();
            res.curElementIndex = curIndex;
            res.curElementValue = sourceDataCopy[curIndex];
            res.sourceDataCopy = sourceDataCopy;
            return res;
        }
        /**
         * 当前被pop元素左边比自己大元素的信息
         * @param leftIndex 当前被pop元素左边比自己大元素的下标
         * @return PushCausePopInfo
         */
        private PushCausePopInfo<T> left(Integer leftIndex) {
            leftGreaterElementIndex = leftIndex;
            if (Objects.nonNull(leftIndex)) {
                leftGreaterElementValue = sourceDataCopy[leftIndex];
            }
            return this;
        }
        /**
         * 当前被pop元素右边比自己大元素的信息
         * @param rightIndex 当前被pop元素右边比自己大元素的下标
         * @return PushCausePopInfo
         */
        private PushCausePopInfo<T> right(Integer rightIndex) {
            rightGreaterElementIndex = rightIndex;
            if (Objects.nonNull(rightIndex)) {
                rightGreaterElementValue = sourceDataCopy[rightIndex];
            }
            return this;
        }

        public Integer getCurElementIndex() {
            return curElementIndex;
        }

        public T getCurElementValue() {
            return curElementValue;
        }

        public Integer getLeftGreaterElementIndex() {
            return leftGreaterElementIndex;
        }

        public T getLeftGreaterElementValue() {
            return leftGreaterElementValue;
        }

        public Integer getRightGreaterElementIndex() {
            return rightGreaterElementIndex;
        }

        public T getRightGreaterElementValue() {
            return rightGreaterElementValue;
        }

        @Override
        public String toString() {
            return "PushCausePopInfo{" +
                    "curElementIndex=" + curElementIndex +
                    ", curElementValue=" + curElementValue +
                    ", leftGreaterElementIndex=" + leftGreaterElementIndex +
                    ", leftGreaterElementValue=" + leftGreaterElementValue +
                    ", rightGreaterElementIndex=" + rightGreaterElementIndex +
                    ", rightGreaterElementValue=" + rightGreaterElementValue +
                    '}';
        }
    }


    public static void main(String[] args) {
        Integer[] array = {8, 4, 3, 4, 5, 3, 5, 6};
        MonotoneStack<Integer> stack = create(array);
        while (true) {
            System.out.println("====");
            stack.pushNextInto().forEach(System.out::println);
            System.out.println("====");
        }
    }
}
